package com.yan_jiu_sheng.LeetCodeHot100.UnionFind;

/**
 * 并查集的数据结构实现
 *
 * @author yulongTian
 * @create 2024-05-24 15:41
 */
public class UF {
    // 连通分量
    private int count;
    // 并查集数组
    private int[] parent;
    // 记录每个连通分量中的节点数
    // 只有每个连通分量的根节点的 size[] 才可以代表该连通分量中的节点数
    private int[] size;

    // 构造函数
    public UF(int n) {
        this.count = n;
        this.parent = new int[n];
        this.size = new int[n];
        for (int i = 0; i < n; i++) {
            // 最初，每个节点均是独立的
            this.parent[i] = i;
            // 最初，每个连通分量均为 1
            this.size[i] = 1;
        }
    }


    /* 将 p 和 q 连接 */
    public void union(int p, int q) {
        int rootP = find(p);
        int rootQ = find(q);
        if (rootP == rootQ) return;


        if (size[rootP] < size[rootQ]) {
            parent[rootP] = rootQ;
            size[rootQ] += size[rootP];
        } else {
            parent[rootQ] = rootP;
            size[rootP] += size[rootQ];
        }
        // 连通分量 -1
        this.count--;
    }

    /* 判断 p 和 q 是否连通 */
    public boolean connected(int p, int q) {
        int rootP = find(p);
        int rootQ = find(q);
        return rootP == rootQ;
    }

    /* 返回图中有多少个连通分量 */
    public int count() {
        return this.count;
    }

    /**
     * 循环实现
     * 返回当前节点的根节点
     *
     * @param x
     * @return
     */
    private int find(int x) {
        while (x != this.parent[x]) {
            // 路径压缩
            parent[x] = parent[parent[x]];
            x = this.parent[x];
        }
        return x;
    }

    /**
     * 递归实现
     *
     * @param x
     * @return
     */
    private int find_01(int x) {
        if (parent[x] != x) {
            parent[x] = find_01(parent[x]);
        }
        return parent[x];
    }

}
